#include<vector>
#include<unordered_set>
#include<deque>
using namespace std;
class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        if (n < 2) return n;
        unordered_set<int> visited[2];
        deque<int>queue;
        int flag = 0;
        for (int i = 0; i < n; ++i) {
            if (visited[flag].find(i) != visited[flag].end()
                || visited[1-flag].find(i) != visited[1-flag].end())
                continue;
            visited[flag].insert(i);
            queue.push_back(i);
            while (!queue.empty()) {
                int size = queue.size();
                while (size > 0) {
                    --size;
                    int node = queue.front();
                    queue.pop_front();
                    for (auto tmp : graph[node]) {
                        if (visited[flag].find(tmp) != visited[flag].end())
                            return false;
                        if (visited[1 - flag].find(tmp) == visited[1-flag].end()) {
                            queue.push_back(tmp);
                            visited[1 - flag].insert(tmp);
                        }
                    }
                }
                flag = 1 - flag;
            }
        }
        return true;
    }
};